home *** CD-ROM | disk | FTP | other *** search
/ Pascal Super Library / Pascal Super Library (CW International)(1997).bin / LIBRARY / FUTILS / FSTACK.DOC < prev    next >
Text File  |  1989-02-19  |  7KB  |  227 lines
  1.                              /\ RKCP /\
  2.                              \/ RKCP \/
  3.  
  4. ********************************************************************
  5. ************************ FSTACK by Rex Kerr ************************
  6. ************************ Copyright (C) 1989 ************************
  7. ********************************************************************
  8.  
  9. This is a Turbo Pascal unit written in assembly language that lets
  10. you create stacks that can be used like the CPU's main stack.  You
  11. can have either byte or word stacks, and you can switch as often as
  12. you like.  You can only have one active byte or words stack at one
  13. time, though.
  14.  
  15. There are 7 routines for word stacks, and seven more for byte stacks.
  16.  
  17. ***
  18.  
  19. InitWStack(var buf; len : word);
  20.  
  21. This initializes the word stack.  Len is the length of buf.  If you
  22. are passing a pointer to something, make sure you pass the something
  23. instead of the pointer;
  24.  
  25. var st : ^string;
  26. begin
  27.      new(st);
  28.      initwstack(st^,sizeof(st^));  { Right. }
  29.      initwstack(st,sizeof(st));    { Now your buffer is the pointer!
  30.                                      You only have 4 bytes! }
  31.      initwstack(st,sizeof(st^));   { This is dangerous!  If you do
  32.                                      too much pushing, you'll run
  33.                                      past the 4 byte pointer ... }
  34.      initwstack(st^,sizeof(st));   { This is horrible!  You have 256
  35.                                      bytes available, but have said
  36.                                      you only have 4 }
  37.      dispose(st);
  38. end.
  39.  
  40. ***
  41.  
  42. InitBStack(var buf; len : word);
  43.  
  44. This is exactly the same as InitWStack, except it initializes the
  45. byte stack.
  46.  
  47. ***
  48.  
  49. ClearWStack;
  50.  
  51. This just clears the word stack.
  52.  
  53. ***
  54.  
  55. ClearBStack;
  56.  
  57. This clears the byte stack.
  58.  
  59. ***
  60.  
  61. WStackEmpty : boolean;
  62.  
  63. This returns true if the word stack is empty.
  64.  
  65. ***
  66.  
  67. BStackEmpty : boolean;
  68.  
  69. This returns true if the byte stack is empty.
  70.  
  71. ***
  72.  
  73. PushW(w : word);
  74.  
  75. This pushes one word onto the word stack (if it isn't full).
  76.  
  77. ***
  78.  
  79. PushB(b : byte);
  80.  
  81. This pushes one byte onto the byte stack (if it isn't full).
  82.  
  83. ***
  84.  
  85. PopW : word;
  86.  
  87. This pops one word from the word stack.  It is a function for
  88. flexibility and speed.
  89.  
  90. ***
  91.  
  92. PopB : byte;
  93.  
  94. This pops one byte from the byte stack.
  95.  
  96. ***
  97.  
  98. WStackSize : word;
  99.  
  100. This returns the current number of entries in the word stack.  To
  101. find the maximum word size do:
  102.  
  103.      Max_Size := sizeof(buf) shr 1;
  104.  
  105. And to find the number of free spaces (assuming you have found
  106. Max_Size) you do:
  107.  
  108.      free_spaces := Max_Size - WStackSize;
  109.  
  110. ***
  111.  
  112. BStackSize : word;
  113.  
  114. BStackSize returns the number of entries in the byte stack.
  115. Max_Size for the byte stack is the same thing as sizeof(buf).
  116.  
  117. ***
  118.  
  119. SetWStack(size : word);
  120.  
  121. You use this for swapping stacks.  Like this:
  122.  
  123. var bufa,bufb : array[1..100] of byte;
  124.     sizea : word
  125. begin
  126.      initwstack(bufa,sizeof(bufa)); { Initialize the stack         }
  127.      ( . . . )                      { Do some stuff to it          }
  128.      sizea := wstacksize;           { Get the size of the stack    }
  129.      initwstack(bufb,sizeof(bufb)); { Re-initialize stack #2       }
  130.      ( . . . )                      { Do whatever with stack #2    }
  131.      initwstack(bufa,sizeof(bufa)); { Back to stack #1, but it's
  132.                                       empty }
  133.      setwstack(sizea);              { Now we're back to the first
  134.                                       stack the way it was }
  135. end.
  136.  
  137. Please note that only pushes actually change the values in the
  138. stack.  The others just set different hidden variables or read
  139. from the stack.  SetWStack just sets the length of the stack to
  140. what size you specify; it in no way changes the contents of the
  141. stack.  ClearWStack just calls SetWStack(0).
  142.  
  143. ***
  144.  
  145. SetBStack(size : word);
  146.  
  147. This does for the byte stack what SetWStack does for the word stack.
  148.  
  149. ***
  150.  
  151. One useful place for this is in a non-recursive form of QuickSort.
  152.  
  153. For short stacks, FSTACK is much better than a linked list stack.
  154. Here are the reasons why:
  155.  
  156. 1) It is much faster (3 or 4 times, I think)
  157. 2) It has no overhead per item
  158. 3) You can access the stack as an array
  159.  
  160. You also can have just the amount of space you want like this:
  161.  
  162. program Get_Just_Enough;
  163. uses fstack;
  164. type stackarry : array[1..100] of byte;
  165. var b : ^stackarry;
  166.     len : word;
  167. begin
  168.      len := 14;                 { Or however much you need }
  169.      getmem(b,len);             { Get the memory           }
  170.      initstack(b^,sizeof(b^));  { Initialize the stack     }
  171.      ( . . . )                  { Use the stack            }
  172.      freemem(b,len);            { Free the memory used     }
  173. end.
  174.  
  175. It isn't a good idea to reallocate b while you are using the stack,
  176. in case the place where b is stored is moved.  If it is moved,
  177. you can fix that with FSWAP.  Like this:
  178.  
  179. uses fswap,fstack;
  180. type stackarry := array[1..100] of word;
  181. { If range checking is off, the 1..100 may be any size.  If it's on,
  182.   it must be at least as large as the largest getmem (to avoid a
  183.   range check error) }
  184. var len,size : word;             { len is to store the getmem value,
  185.                                    size is to store wstacksize }
  186.     b,temptr : ^stackarry;       { You'll need the extra pointer }
  187. begin
  188.      len := 14;           { Set getmem length                     }
  189.      getmem(b,len);       { Get the memory                        }
  190.      initwstack(b^,len);  { Initialize the stack                  }
  191.      ( . . . )            { Use the stack & find it is too small  }
  192.      temptr := b;         { Save the address of the buffer        }
  193.      freemem(b,len);      { Free the buffer's memory              }
  194.      len := 28;           { Set the new length                    }
  195.      getmem(b,len);       { Get the memory                        }
  196.      size := wstacksize;  { Get the stack size                    }
  197.      if temptr <> b then  { If temptr <> b, the b has been moved  }
  198.      begin
  199.           qswapv(temptr,b,size);   { Move the stack values to the
  200.      end;                            new location }
  201.      initwstack(b^,len);  { Re-initialize the stack to the new
  202.                             maximum length (and maybe location)   }
  203.      setwstack(size);     { Set the stack to use the old pushed
  204.                             values                                }
  205.      ( . . . )            { Do whatever you want                  }
  206.      freemem(b,len);      { Free the allocated memory             }
  207. end.                      { We're done.                           }
  208.  
  209. All of the byte stack things work just like the word stack things,
  210. except you push and pop bytes.  You will probably have to use
  211. value typecasting (for things like characters and integers).
  212. And also you'll have to split things like longints up.  When you
  213. are doing that, remember that if you push the high part first and
  214. then the low part, you should pop the low part and then the high
  215. part to get it back the same way.
  216.  
  217. I've thought of a zillion things to use this for, and I'm hoping
  218. it will be just as useful to everyone else.
  219.  
  220. If I seem to have left something out or if things are unclear please
  221. let me know via CompuServe on either EasyPlex or BPROGAs TP5 message
  222. section.
  223.  
  224. Rex Kerr  71550,3147
  225.  
  226.                              /\ RKCP /\
  227.                              \/ RKCP \/